package linkedlist;

/**
 * L0 → L1 → … → Ln - 1 → Ln
 * 请将其重新排列后变为：
 * L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
 * 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
 */
public class no143 {
    public void reorderList(ListNode head) {
        if(head == null || head.next == null || head.next.next == null){
            return;
        }
        int size = 0;
        ListNode cur = head;
        while (cur != null){
            size++;
            cur = cur.next;
        }
        size = (size+2)/2;
        cur = head;
        while (size-1 > 0){
            cur = cur.next;
            size--;
        }
        ListNode afterHead = cur.next;
        cur.next = null;
        cur = head;
        ListNode prev = afterHead;
        ListNode newNode = afterHead;
        ListNode next = null;
        // 逆置后面的链表
        while (prev != null){
            newNode = newNode.next;
            prev.next = next;
            next = prev;
            prev = newNode;
        }

        afterHead = next;
        prev = afterHead;

        while (afterHead != null){
            prev = prev.next;
            afterHead.next = cur.next;
            cur.next = afterHead;
            cur = afterHead.next;
            afterHead = prev;
        }
    }
}
